package com.arron.algorithm.leetcodetop100.二叉树;

import com.arron.algorithm.ListNode;
import com.arron.algorithm.tree.TreeNode;


/**
 * 108. 将有序数组转换为二叉搜索树
 *
 * 109. 有序链表转换二叉搜索树
 *
 */
public class SortedArrayOrListNodeToBST {



    ListNode temp = null;

    /**
     * 将有序数组转换为二叉搜索树
     * @param nums
     * @return
     */
    public TreeNode sortedArrayToBST(int[] nums) {

        TreeNode treeNode = sortedArrayToBST(nums, 0, nums.length - 1);

        return treeNode;
    }

    public TreeNode sortedArrayToBST(int[] nums,int start,int end){


        if (start>end){
            return null;
        }
        if (start == end){
            return new TreeNode(nums[start]);
        }

        int mid = start+ (end-start)/2;
        TreeNode node = new TreeNode(nums[mid]);
        node.left = sortedArrayToBST(nums,start,mid-1);
        node.right = sortedArrayToBST(nums,mid+1,end);
        return node;
    }

    public static void main(String[] args) {

        SortedArrayOrListNodeToBST sortedArrayOrListNodeToBST = new SortedArrayOrListNodeToBST();
        int[] nums = {-10,-3,0,5,9};
        TreeNode treeNode = sortedArrayOrListNodeToBST.sortedArrayToBST(nums);
        System.out.println(treeNode);


    }


    /**
     * 有序链表转换二叉搜索树
     * @param head
     * @return
     */
    public TreeNode sortedListToBST(ListNode head) {

       return sortedToBST(head);
    }

    public TreeNode sortedToBST(ListNode head){
        if (head == null){
            return null;
        }else if(head.next == null){
            return new TreeNode(head.val);
        }


        ListNode pre = head; //这个节点很重要，不然容易出现空指针
        ListNode slow = head.next;
        ListNode fast = slow.next;
        while (fast!=null && fast.next!=null){
            pre = pre.next;
            slow = pre.next;
            fast = fast.next.next;
        }
        TreeNode treeNode = new TreeNode(slow.val);

        treeNode.right = sortedListToBST(slow.next);
        //断链,断掉中间节点左边
        pre.next = null;
        treeNode.left = sortedListToBST(head);
        return treeNode;
    }


    public ListNode getMidNode(ListNode left,ListNode right){

        ListNode slow = left;
        ListNode fast = left.next;

        while (fast !=right && fast.next != right){

            slow = slow.next;
            fast = fast.next.next;

        }
        return slow;


    }

}
